//等差数列划分
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //f(x)表示以x位置元素为结尾的所有子数组中等差数列的个数
        int n = nums.size();
        vector<int> dp(n);
        int retVal = 0;
        for(size_t i = 2 ; i < n ; ++i)
        {
            if(nums[i-1]-nums[i-2] == nums[i] - nums[i-1])
            {
                dp[i] = dp[i-1]+1;
            }
            else 
            {
                dp[i] = 0;
            }
            retVal += dp[i];
        }
        return retVal;
    }
};
//最长湍流子数组
class Solution {
public:
    bool IsTurbulence(int num1,int num2,int num3)
    {
        if((num1 > num2 && num3 > num2)||(num1 < num2 && num3 < num2))
            return true;
        return false;
    }
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n);
        auto g = f;
        f[0] = g[0] = 1;
        int retVal = f[0];
        for(size_t i = 1 ; i < n ; ++i)
        {
            if(arr[i] > arr[i-1])
            {
                f[i] = g[i-1]+1;
                g[i] = 1;
            }
            else if(arr[i] < arr[i-1])
            {
                f[i] = 1;
                g[i] = f[i-1]+1;
            }
            else 
            {
                f[i] = 1;
                g[i] = 1;
             }
            if(f[i] > retVal)
                retVal = f[i];
            if(g[i] > retVal)
                retVal = g[i];
        }
        return retVal;
    }
};
//单词划分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(),wordDict.end());
        int n = s.size();
        vector<bool> dp(n+1,true);
        s = ' ' + s;
        int j = 1;
        for(size_t i = 1 ; i <= n ; ++i)
        {
            for(size_t j = i ; j >= 1 ; --j)
            {
                if(dp[j-1] && dict.count(s.substr(j,i-j+1)))
                {
                    std::cout << s.substr(j,i-j+1) << std::endl;
                    dp[i] = true;
                    break;
                }
                else 
                {
                    dp[i] = false;
                }
            }
        }
        return dp[n];
    }
};
//环绕字符串中唯一的子字符串
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n,1);
        vector<int> nums(26);
        nums[s[0]-'a'] = 1;
        int retVal = 0;
        for(size_t i = 1 ; i < n ; ++i)
        {
            if(s[i]-1 == s[i-1] || s[i] == 'a' && s[i-1] == 'z')
            {
                dp[i] += dp[i-1];
                std::cout << s[i]-'a' << std::endl;
            }
            if(nums[s[i]-'a'] < dp[i])
                nums[s[i]-'a'] = dp[i];
        }
        for(auto& e : nums)
        {
            retVal += e;
        }
        return retVal;
    }
};









